1. Field of the Invention
The present invention relates to an encoder and a decoder for realizing an error-correction encoding and decoding system for processing an error-correcting code, the code being made by superimposing error-correcting codes respectively generated from a couple of pieces of information and a decoding system utilizing such a decoder.
2. Discussion of Related Art
FIG. 1 shows an example of a code format utilizing a product code, i.e., first information I.sub.p, which is required to be highly reliable, and second information I.sub.s, which is not required to have such a high reliability. See Peterson et al., Error-Correcting Codes p. 131-136 (MIT Press, 1972). As shown in FIG. 1, first information I.sub.p of k.sub.1 .times.k.sub.2 digits is encoded by a product code. Namely, this first information I.sub.p is encoded to a product code, having as a partial code, a linear code C.sub.11 having a code word length n.sub.11, information code length k.sub.1, and minimum code length d.sub.11 (hereinafter a linear code of code word length N, information code length K, and minimum code length D will be called a (N, K, D) linear code C). First information I.sub.p also has (n.sub.2, k.sub.2, d.sub.2) linear code C.sub.2 as a partial code. The composite minimum distance is d.sub.11 .multidot.d.sub.2.
On the other hand, second information I.sub.s of r.times.k.sub.x digits (r&lt;n.sub.11 -k.sub.1) is encoded to a block code, e.g., a (n.sub.2, k.sub.x, D) linear code C.sub.3 on a Galois field GF(2.sup.r). In this case, the product code and linear code C.sub.3 are not superimposed with each other and are transmitted separately.
FIG. 2 shows an example of a code format for encoding first information I.sub.p and second information I.sub.s using a superimposed code, introduced, for example, by M. Kasahara, et al., "New Classes of Binary Codes Constructed on the Basis of Concatenated Codes and Product Codes," IEEE Transaction on Information Theory, Vol, IT -22, No. 4, p. 462-468 (July 1976). In this case, first information I.sub.p is encoded to a product code of the compound minimum distance d.sub.1 .multidot.d.sub.2 by using the partial codes (n.sub.1, k.sub.1, d.sub.1) linear code C.sub.1 and (n.sub.2, k.sub.2, d.sub.2) linear code C.sub.2. Second information I.sub.s of (n.sub.1 -k.sub.1).times.(n.sub.2 -(d.sub.1 .multidot.d.sub.2 -1)) digits is encoded by an RS (Reed-Solomon) code on GF(2.sup.r) of the minimum distance d.sub.1 .multidot.d.sub.2 -1. Here, r=n.sub.1 -k.sub.1 and a code word C.sub.s of the RS code is superimposed on a check field C.sub.h (hatched portion in FIG. 2) of the product code.
Next, an encoding operation will be explained. First information I.sub.p is encoded to a product code, while second information I.sub.s is encoded to an (n.sub.2, n.sub.2 -d.sub.1 .multidot.d.sub.2 +1, d.sub.1 .multidot.d.sub.2 -1) RS code on GF(2.sup.r ). A code word of the product code is C.sub.p and a code word of the RS code is C.sub.s. Code word C.sub.s is superimposed on code check field C.sub.h (C.sub.h is assumed to include a check field of linear code C.sub.1 and an internal check field for this check field). After such superimposing the resulting code word C.sub.y is transmitted to a transmission line.
Here, the i-th symbol R.sub.i of code word C.sub.s is expressed as R.sub.i =(R.sub.i1, R.sub.i2, . . . , R.sub.ir), and M.sub.i is defined as follows: ##EQU1##
.sym. means modulo-2 sum and H.sub.i designates a symbol of check field C.sub.h. Moreover, F.sub.i is defined as follows: EQU F.sub.i =(I.sub.i, M.sub.i)
I.sub.i is an information symbol of linear code C.sub.1. Therefore, code word C.sub.y may be expressed as a vector (F.sub.1, F.sub.2 , . . . , F.sub.q) where q=n.sub.2.
In addition, the article in the IEEE journal, cited above, provides the following theorem:
Theorem: If a product code is capable of correcting up to t errors a code after the superimposing can correct errors when the minimum distance D.sub.1 satisfies the relationship t=[(D.sub.1 -1)/2.
Next, a decoding operation will be explained. Here, re-encoding a received information symbol series is called "separation encoding." Further, recovering the internal check by separation encoding is called "internal check recovery," while separation of a superimposed received word by modulo-2 sum of an internal check symbol and a received word is called "superimposing separation." An error newly added to a superimposed code word at the time of superimposing separation due to an error generated at the information symbol of the basic code is called a "pseudo-error." This pseudo-error coincides with a syndrome.
A detailed explanation will be made with reference to a flowchart of FIG. 3 and an explanatory drawing of FIG. 4. A received word C.sub.y is shown in FIG. 4(a). In this figure, the hatched area indicates a redundant field. First, as shown in FIG. 4(b), separation encoding is carried out for each of the n.sub.2 lines in a C.sub.1 separation-encoding routine (step ST11) to obtain an internal check recovery symbol H.sub.i. Next, in a superimposing separation routine (step ST12), as shown in FIG. 4(c), internal check recovery symbol H.sub.i is modulo-2 summed with a check field M.sub.i of received word C.sub.y in order to separate a received word C.sub.s of the superimposed code. In a superimposed code decoding routine (step ST13), received word C.sub.s is decoded to obtain a decoded word C.sub.s and information I.sub.s is output as shown in FIG. 4(d).
Moreover, a received word C.sub.p of the product code is separated in a product code recovery routine (step ST14) by modulo-2 summing decoded word C.sub.s with check field M.sub.i of received word C.sub.y. At this time, as shown in FIG. 4(e), a C.sub.1 code check field H.sub.i of the product code is recovered. Next, received word C.sub.p is decoded in a C.sub.1 decoding routine (step ST15) to obtain an intermediate received word I.sub.p as shown in FIG. 4(f). Intermediate received word I.sub.p is decoded and information I.sub.p as shown in FIG. 4(g) is output in a C.sub.2 decoding routine (step ST16).
In the case where first information I.sub.p is not superimposed by information obtained by encoding second information I.sub.s, sufficient error-correcting capability cannot be exerted if error-correction encoding is not carried out by providing a wide check field because encoding is conducted with a code perfectly separating information I.sub.p and I.sub.s.
Although the encoding and decoding explained with reference to FIGS. 2-4 can remarkably reduce redundancy of a product code if the code word of information I.sub.s is superimposed on the check field of the product code, the minimum distance of the superimposed code must be set as large as d.sub.1 .multidot.d-1 in order to transmit information I.sub.s, thereby necessitating complicated hardware.
Furthermore, in Kashara after internal check recovery symbol H.sub.i is generated, received word C.sub.s is separated from internal check recovery symbol H.sub.i, and the product code must be recovered by adding decoded word C.sub.s to received C.sub.y.
Consequently very complicated processing is required to finally obtain information I.sub.p and I.sub.s as well as requiring a longer decoding time.